package devideconquer;

public class MaximumSubarrayFinder {
	/**
	 * 使用一个循环来查找最大子数组,时间复杂度为O(n),空间复杂度为O(1)
	 * @param numbers
	 * @return
	 */
	public static Tag findMaximumSubarray1(int[] numbers)
	{
		Tag maxSubarray = new Tag(0, 0, numbers[0] > 0 ? numbers[0] : 0);
		Tag tailingMaxSubarray = (Tag)maxSubarray.clone();
		
		for(int i = 1; i < numbers.length; i ++)
		{
			tailingMaxSubarray.to = i;
			if(numbers[i] <= - tailingMaxSubarray.sum)
			{
				tailingMaxSubarray.from = i + 1;
				tailingMaxSubarray.sum = 0;
			}
			else
			{
				tailingMaxSubarray.sum += numbers[i]; 
			}
			
			if(maxSubarray.sum < tailingMaxSubarray.sum)
			{
				maxSubarray.from = tailingMaxSubarray.from;
				maxSubarray.to = tailingMaxSubarray.to;
				maxSubarray.sum = tailingMaxSubarray.sum;
			}
		}
		
		return maxSubarray;
	}

	/**
	 * 使用递归的方法查找子数组,复杂度为O(nlgn),空间复杂度为O(n)
	 * @param numbers
	 * @return
	 */
	public static Tag findMaximumSubarray2(int[] numbers)
	{
		return findMaximumSubarray2(numbers, 0, numbers.length - 1);
	}
	
	public static Tag findMaximumSubarray2(int[] numbers, int low, int high)
	{
		if(low == high)
			return new Tag(low, high, numbers[low]); 
		
		int mid = (high + low) / 2;
		Tag tagLeft = findMaximumSubarray2(numbers, low, mid);
		Tag tagRight = findMaximumSubarray2(numbers, mid + 1, high);
		Tag tagMid = findMaximumCrossingSubarray(numbers, low, mid, high);
		
		if(tagLeft.sum >= tagRight.sum && tagLeft.sum >= tagMid.sum)
			return tagLeft;
		else if(tagRight.sum >= tagLeft.sum && tagRight.sum >= tagMid.sum)
			return tagRight;
		else
			return tagMid;
	}
	
	public static Tag findMaximumCrossingSubarray(int[] numbers, int low, int mid, int high)
	{
		int sum = 0;
		int sumLeft = Integer.MIN_VALUE;
		int indexLeft = 0;
		for(int i = mid; i >= low; i --)
		{
			sum += numbers[i];
			if(sum > sumLeft)
			{
				sumLeft = sum;
				indexLeft = i;
			}
		}
		
		sum = 0;
		int sumRight = Integer.MIN_VALUE;
		int indexRight = 0;
		for(int i = mid + 1; i <= high; i ++)
		{
			sum += numbers[i];
			if(sum > sumRight)
			{
				sumRight = sum;
				indexRight = i;
			}
		}
		
		return new Tag(indexLeft, indexRight, sumLeft + sumRight);
	}
	
	public static void main(String[] args) {
		int[] numbers = new int[]{0,-5,-3,2, 1, -2, 8,-6};
		
		Tag tag = findMaximumSubarray2(numbers);
		System.out.println(tag);
	}
}
